package edu.cityu.cs.hk.datastructures;
/** 
 * Interface for a deque (double-ended queue).  A deque is a
 * collection of linearly arranged elements that are accessed,
 * inserted, and removed at the beginning or at the end.
 *
 * @author Michael T. Goodrich
 * @author Mark Handy
 * @author Roberto Tamassia
 * @see EmptyDequeException
 * @see Queue
 * @see Stack

 */

public interface Deque {

  // accessor methods

/** 
 * Gets the first element (without modifying the deque).
 *
 * @return first element in the deque.
 * @exception EmptyDequeException if the deque is empty
 */
  public Object first()  
    throws EmptyDequeException; 

/** 
 * Gets the last element (without modifying the deque).
 *
 * @return last element in the deque.
 * @exception EmptyDequeException if the deque is empty
 */
  public Object last()  
    throws EmptyDequeException;  

/** 
 * Tests if this deque is empty
 *
 * @return <code>true</code> if the deque is empty, <code>false</code>
 * otherwise.
 */
  public boolean isEmpty();  


/** 
 * Gets the number of elements. 
 *
 * @return  number of elements in the deque.
 */
  public int size();  

  // update methods

/** 
 * Insert an element at the beginning.
 *
 * @param element new element to be inserted.
 */
  public void insertFirst (Object element);  

/** 
 * Insert an element at the end.
 *
 * @param element new element to be inserted.
 */
  public void insertLast (Object element);  

/** 
 * Remove the element at the beginning.
 *
 * @return element removed.
 * @exception EmptyDequeException if the deque is empty
 */
  public Object removeFirst()  
    throws EmptyDequeException; 

/** 
 * Remove the element at the end.
 *
 * @return element removed.
 * @exception EmptyDequeException if the deque is empty
 */
  public Object removeLast()  
    throws EmptyDequeException;  

}
